#include "main.h"

Array findLongestSubsequence(Array& array1, Array& array2)
{
	Array* a1 = &array1;
	Array* a2 = &array2;
	int minLen = array1.len;
	int maxLen = array2.len;
	if (minLen > array2.len)
	{
		minLen = array2.len;
		maxLen = array1.len;
		a1 = &array2;
		a2 = &array1;
	}
	
	Array buf1(minLen);
	Array buf2(minLen);
	Array* currBuf = &buf1;
	Array* lastBuf = &buf2;
	for (int i = 0; i < maxLen; ++i)
	{
		if ((*a1)[0] == (*a2)[i])
		{
			(*currBuf)[0] = 1;
		}
		for (int j = 1; j < minLen; ++j)
		{
			if ((*a1)[j] == (*a2)[i])
			{
				(*currBuf)[j] = (*lastBuf)[j-1] + 1;
			}
			else
			{
				(*currBuf)[j] = ((*currBuf)[j-1] > (*lastBuf)[j]) ? (*currBuf)[j-1] : (*lastBuf)[j];
			}
		}
		Array* a = currBuf;
		currBuf = lastBuf;
		lastBuf = a;
	}
	
	Array resArray((*lastBuf)[lastBuf->len-1]);
	
	buf1.clean();
	buf2.clean();
	
	return resArray;
}